package leetcode.templates.trees;

import leetcode.helper.tree.TreeNode;

/**
 * 二分判断树上节点是否存在，利用数字101011,从高二1(01011)位0向左，1向右的特性。<br>
 * 根节点是1
 *
 * @author CaoYu
 * @date 2022年3月21日
 * @description
 */
public class MaxBinarySearchNode {

	public int countNodes(TreeNode root) {
		if (root == null) {
			return 0;
		}
		TreeNode node = root;
		int h = 0;
		while (node.left != null) {
			node = node.left;
			h += 1;
		}
		int l = (int) Math.pow(2, h);
		int r = l * 2 - 1;
		int ans = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			boolean exists = this.find(mid, root, h);
			if (exists) {
				r = mid - 1;
			} else {
				ans = mid;
				l = mid + 1;
			}
		}
		return ans;
	}

	private boolean find(int num, TreeNode root, int h) {
		int check = 1 << (h - 1);
		TreeNode node = root;
		while (check > 0) {
			node = (num & check) == 0 ? node.left : node.right;
			check >>= 1;
		}
		return node == null;
	}

}
